Năm 194, sứ quân Lã Bố chiếm căn cứ của Tào Tháo ở Duyện Châu, với sự giúp đỡ từ Trần Cung, Trương Mạc trong khi Tào Tháo đang đi đánh Đào Khiêm tại Từ Châu. Nhạc Tiến và Tào Hồng được giao làm tiên phong chiếm lại Duyện Châu. Tào Tháo và Lã Bố đã đánh nhiều trận tại thành Bộc Dương, quân Tào tuy thua nhiều hơn thắng, nhưng những đóng góp của Nhạc Tiến vẫn được ghi nhận bởi Tào Tháo. Nhạc Tiến tham gia đánh Trương Siêu, là em của Trương Mạc tại Ung Khẩu và Kiều Duệ tại Châu quận, ông đều làm tiên phong và là người đầu tiên phá vỡ đội hình của đối phương ở cả hai trận trên. Nhạc Tiến được phong làm "Quảng Xương Đình Hầu" (廣昌亭侯), được đánh giá cao trong quân Tào.

Năm 197-198, Nhạc Tiến theo Tào Tháo đánh Trương Tú, người đã giả hàng và đánh bại Tào Tháo trong trận Uyển Thành. Trải nhiều khó khăn trong trận này, nhưng Nhạc Tiến cùng Vu Cấm đạt nhiều công lao. Biết rằng Trương Tú được chống lưng bởi Lưu Biểu, thái thú Kinh Châu, Tào Tháo biết rằng chưa thể đánh Trương Tú trong một sớm một chiều. Trong khi Lưu Bị nhờ Tào Tháo chống lại Lã Bố ở Tiểu Phì, Tào Tháo quyết định giảng hòa với Trương Tú, còn kết làm đồng minh và kết giao bằng hôn nhân, mà Trương Tú cũng ưng thuận. Trong trận vây Hạ Phì của Lã Bố, Nhạc Tiến dẫn một toán binh riêng lẻ đánh bại được một tướng của Lã Bố trước khi tham gia bao vây.

Sau khi Lã Bố chết, Tào Tháo quay sang ứng phó với Viên Thiệu, khi ấy vẫn là đồng minh của Tào, Nhạc Tiến được điều ra biên giới giữa Viên-Tào. Khi đó, Thái thú Biện Châu là Trương Dương, phân vân không biết nên kết đồng minh với Tào hay Viên, bị thuộc hạ là Dương Châu giết đi, cắt đầu đem hàng Tào Tháo. Trả thù cho chủ, Tùy Cố bèn giết Dương Châu rồi lại hàng Viên Thiệu ở phía Bắc. Nhạc Tiến liền đem quân truy kích Tùy Cố, thu phục được quân sĩ Biện Châu. Nhạc Tiến hợp binh với Tào Tháo đánh Lưu Bị, người vừa giết Thái thú Từ Châu là Xa Trụ. Chỉ trong một thời gian ngắn, Lưu Bị đã bị đánh bại, phải nương nhờ Viên Thiệu, bộ tướng của Lưu Bị là Quan Vũ bị bắt sống. Nhạc Tiến được phong làm Đãng Khấu Hiệu Úy (討寇校尉).